Complex Event Processing (“CEP”) is an event processing concept that deals with the task of processing multiple events (i.e., an event cloud) with the goal of identifying meaningful events within the event cloud. The event cloud may, for example, be an incoming stream of data received by an application and a CEP system may identify complex sequences of events in real-time. CEP systems employ techniques such as detection of complex patterns of events, event correlation and abstraction, event hierarchies, and relationships between events such as causality, membership and timing, and event-driven processes. CEP systems may be used to discover information trends contained in the events happening across all layers in an organization and then analyze an event's impact from a macro level as a “complex event.” Thus, action may be take in real-time to respond to the complex event.
CEP is becoming crucial in enterprise-scale applications. However, processing the multitude of events that stream into an enterprise system within the least possible time is a daunting task. Current enterprise-scale applications desire a rate of gigabytes per second (“GB/sec”). Algorithms and systems have aspired to achieve high scalability and high performance but such systems are complex and expensive. The main component of a CEP system is event matching, for example utilizing a correlation engine (“CE”) which matches and identifies patterns in the incoming event stream. The CE has to process a large number of events per second and analyze different event processing strategies. Hence, the CE has to provide high scalability, availability, and performance.
Systems and algorithms have been suggested in attempts to achieve high scalability and performance. For example, “Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems”, by F. Fabret, et al., AMC SIGMOND, 2001, the entire contents of which are incorporated herein by reference, describes filtering algorithms and implementations for a CEP system. “Parallel Event Processing for Content-Based Publish/Subscribe Systems”, by A. Farroukh, et al., AMC DEBS 2009, the entire contents of which are incorporated herein by reference, describes a parallel matching engine for a CEP system which leverages chip multi-processors to increase throughput and reduce matching time. The Fabret and Farroukh articles teach similar two-phase algorithms for pattern matching and Farroukh additionally teaches using event parallel processing.
The articles teach a two-phase algorithm for pattern matching of events in a subscription system. According to the algorithm, a predicate P, an access predicate, has to be matched before a set of subscriptions can be satisfied. An action can be taken on an event only if some condition is met. The algorithm defines a subscription as a set of predicates of the form {<attribute name> A, <value> V, <relational operator (e.g., ≦, ≧, =)> R} and an event is defined by a set of {<attribute name> A, <value> V}. Thus, an event is said to match a predicate when A[e]=A[p] and V[e] R V[p]. In the first phase of the algorithm, the algorithm creates a bit vector to keep track of all predicates that are matched by an event and initializes the bit vector to 0. For every event attribute, the algorithm hashes the attribute name to determine the table holding the attribute and the resulting table is accessed. Entries matched by this attribute are then indexed and corresponding bits in the bit vector are set to 1. In the second phase, the list of access predicates is traversed and matched against the bit vector. When an access predicate matches a corresponding bit vector (i.e., the corresponding bit vector position is set to 1), each set of methods is evaluated. If no match is found, no method is processed.
In a CEP system, maximum time and resources are consumed in the matching and processing engine that connects decoupled entities/events. A CEP system can increase throughput of event processing by utilizing a chip-multiprocessor's multiple cores or grid computing to handle these heavy computations in parallel. Still, implementing CEP systems on conventional hardware, such as chip-multiprocessors, using naïve multithreading is expensive and greater event matching speeds are desired.